
//948.令牌放置
class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        //当能量不够时，保证每次都使用1分都获取最大的能量
        //当能量充足的时候，使用能量换取最小的令牌来获得1分，这样就可以使得利益最大化
        int n=tokens.size();
        sort(tokens.begin(),tokens.end());  //先进行排序
        int left=0,right=n-1;
        int ret=0;
        while(left<right)
        {
            if(power<tokens[left])  //能量不够，用得分获得最多能量
            {
                if(ret==0) return 0;
                ret--;
                power+=tokens[right--];
            }

            power-=tokens[left++]; //用最小能量获取得分
            ret++;
        }
        if(left==right&&power>=tokens[left]) ret++;  //判断相等位置是否还可以获得得分
        return ret;
    }
};